R树是处理多维数据的B+树的改进,是一种高度平衡的数据结构,其所有叶结点处于同一层. R树的搜索码是区间的集合,一个区间是一维.可以把搜索码看成是一个被这些区间包围的方框. 一个数据项的形式为
<n维方框I,rid>
rid标识一个对象,方框I是包含这个对象的最小方框,数据项存储在叶子结点. 非叶子结点包含的索引项形式为
<n维方框I,指向子结点的指针>
此时方框I是包含所有与孩子结点相关联的所有方框的最小方框.
R树是基于虚表实现的,它的数据存储在3个表中. 3个表分别为:
1.Node表存储结点信息,根结点nodeno为1
(nodeno int, data BLOB)
2.Parent表存储结点的父结点信息
(nodeno int, parentnode int)
3.Rowid表存储结点行号
(rowid int,nodeno int)